package com.leetcode.algorithm.y22.m07.w4;

/**
 * 238. 除自身以外数组的乘积
 * 
 * https://leetcode.cn/problems/product-of-array-except-self/
 * 
 * @author jie.deng
 *
 */
class Question0238Solution02 {

	public int[] productExceptSelf(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return new int[] { 0 };
		}
		int[] prefixMul = new int[len - 1];
		prefixMul[0] = nums[0];
		for (int i = 1; i < len - 1; i++) {
			prefixMul[i] = prefixMul[i - 1] * nums[i];
		}
		int[] postfixMul = new int[len];
		postfixMul[len - 1] = nums[len - 1];
		for (int i = len - 2; i > 0; i--) {
			postfixMul[i] = postfixMul[i + 1] * nums[i];
		}

		int[] arr = new int[len];
		arr[0] = postfixMul[1];
		for (int i = 1; i < len - 1; i++) {
			arr[i] = prefixMul[i - 1] * postfixMul[i + 1];
		}
		arr[len - 1] = prefixMul[len - 2];
		return arr;
	}

}